package data;

/**
 * 二分查找树
 * @author Tang Jiujia
 * @since 13:32 2020-04-21
 */
public class BinarySearchTree {

    private Node tree;

    /**
     * 查找指定值的节点
     *
     * @param data
     * @return data.BinarySearchTree.Node
     */
    public Node find(int data) {
        Node p = tree;
        while (p != null) {
            if (data < p.data) {p = p.left;}
            else if (data > p.data) {p = p.right;}
            else { return p; }
        }
        return null;
    }

    /**
     * 查找树中值最小的节点
     */
    public Node findMin() {
        if (tree == null) return null;
        Node p = tree;
        while (p.left != null) p = p.left;
        return p;
    }

    public Node findMax() {
        if (tree == null) return null;
        Node p = tree;
        while (p.right != null) p = p.right;
        return p;
    }

    /**
     * 删除指定值的节点
     *
     * @param data
     */
    public void delete(int data) {
        //指向要删除的节点，初始化指向根节点
        Node p = tree;
        //p节点的父节点
        Node pp = null;
        //查找到值为data的节点
        while (p != null && p.data != data) {
            pp = p;
            if (p.data < data) p = p.right;
            else p = p.left;
        }
        if (p == null) return;

        //要删除的节点有两个子节点
        if (p.left != null && p.right !=null) {
            //查找右子树节点中的最小节点
            Node minP = p.right;
            Node minPP = p;
            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data;
            p = minP;
            pp = minPP;
        }

        //删除节点是叶子节点或者仅有一个子节点
        Node child; //p节点的子节点
        if (p.left != null) child = p.left;
        else if(p.right != null) child = p.right;
        else child = null;

        //如果删除的是根节点
        if (pp == null) tree = child;
        else if(p == pp.left) pp.left = child;
        else pp.right = child;
    }

    /**
     * 向树中插入指定值
     *
     * @param data
     */
    public void insert(int data) {
        if (tree == null) {
            tree = new Node(data);
            return;
        }
        Node p = tree;
        while (p != null) {
            if (data > p.data) {
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            } else {
                if (p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }
        }
    }

    /**
    * 节点
    * */
    public static class Node {
        private int data;
        private Node left;
        private Node right;
        public Node(int data) {
            this.data = data;
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(4);
        tree.insert(5);
        tree.insert(3);
        tree.insert(1);
        tree.insert(9);
        tree.insert(7);
        tree.insert(10);
        System.out.println(tree.findMax().data);
        tree.delete(10);
        System.out.println(tree.findMax().data);
    }
}
